package com.promote.algorithm;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Vector;

/**
 * @ClassName Merge
 * Description 合并区间
 * @Author LiZiHao
 * Date 2022/12/1 13:46
 * @Version 1.0
 **/
public class Merge {
    /**
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
     * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
     *
     * @param intervals
     * @return
     */
    public static int[][] merge(int[][] intervals) {

        if (intervals.length == 0) {
            return intervals;
        }
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));//按每行的第0列升序排序
        Vector<int[]> integerVector;//由于我们事先不知道数组大小，所以用Vector类实现动态数组。
        integerVector = new Vector<>();
        int[] ints = intervals[0];//定义一个Int类型数组用于作比较，默认值为第一组二维数组的值。
        for (int i = 1; i < intervals.length; i++) {//循环这个二维数组
            if (ints[1] >= intervals[i][0]) {//如果第一个数组的右端点大于等于下一个数组的左端点，做说明两个数组有所交集。
                ints[1] = Math.max(ints[1], intervals[i][1]);//int类型数组的右端点等于两个数组中右端点大的那个值。
            } else {
                integerVector.add(ints);//把int类型一维数组ints添加到我们创建的vector类里面。
                ints = intervals[i];//给一维数组重新赋值。
            }
        }
        integerVector.add(ints);//把最后一个区间添加到Vector里面
        return integerVector.toArray(new int[integerVector.size()][2]);//把vector转换成二维数组返回。
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};

        int[][] merge = merge(intervals);

        System.out.println(JSON.toJSONString(merge));
    }

}
